package com.leetcode.algorithm.y22.m06;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * 496. 下一个更大元素 I
 * 
 * https://leetcode.cn/problems/next-greater-element-i/
 * 
 * @author jie.deng
 *
 */
class Question0496Solution01 {

	public int[] nextGreaterElement(int[] nums1, int[] nums2) {
		int len1 = nums1.length;
		int len2 = nums2.length;

		// K=nums2[i] V=nums2中的下一个更大元素
		Map<Integer, Integer> nextGreaterElementMap = new HashMap<>();

		// 单调递增栈，栈中存的是=nums2中的元素，且栈顶元素 > 栈底元素
		Stack<Integer> ascendingStack = new Stack<>();
		nextGreaterElementMap.put(nums2[len2 - 1], -1);
		ascendingStack.push(nums2[len2 - 1]);

		for (int i = len2 - 2; i >= 0; i--) {
			int nextGreaterElement = push2AscendingStack(ascendingStack, nums2[i]);
			nextGreaterElementMap.put(nums2[i], nextGreaterElement);
		}

		int[] retNums = new int[len1];
		for (int i = 0; i < len1; i++) {
			retNums[i] = nextGreaterElementMap.get(nums1[i]).intValue();
		}
		return retNums;
	}

	private int push2AscendingStack(Stack<Integer> ascendingStack, int num) {
		while (!ascendingStack.isEmpty() && ascendingStack.peek().intValue() < num) {
			ascendingStack.pop();
		}
		int nextGreaterElement = -1;
		if (!ascendingStack.isEmpty()) {
			nextGreaterElement = ascendingStack.peek().intValue();
		}
		ascendingStack.push(num);
		return nextGreaterElement;
	}

}